package 力扣.动态规划;

//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
//
//字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
// （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

public class 判断子序列 {
    public static void main(String[] args) {
          String s="abc";
          String t="ahbgdc";
        boolean b = isSubsequence(s, t);
        System.out.println(b);
    }
    public static boolean isSubsequence(String s, String t) {
         int m=s.length();
         int n=t.length();
         int[][] dp = new int[n+1][m+1];
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {
                if (t.charAt(i-1)==s.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n][m]==m;
    }
}
